<?php
/**
 * Created by excalibur
 * User: Yang Renqing
 * Email: yangrenqing@ihappy.net.cn
 * Date: 2019/8/14
 * Time: 4:36 PM
 */
ini_set('memory_limit', '1024M');
function quickSort(&$arr, $left, $right){
    if($left< $right){
        $i = $left;
        $j = $right;
        $index = $arr[$left];
        while($i < $j){
            while($i < $j && $arr[$j] >= $index){
                $j--;
            }
            if($i < $j){
                $arr[$i] = $arr[$j];
            }
            while($i < $j && $arr[$i] <= $index){
                $i++;
            }
            if($i < $j){
                $arr[$j] = $arr[$i];
            }
        }
        $arr[$i] = $index;

        quickSort($arr,$left,$i-1);
        quickSort($arr,$i+1,$right);
    }
}

$start = microtime(true);

$content = file_get_contents("./137.txt");
$allArr = explode(PHP_EOL,$content);
$topArr = array_slice($allArr,0,999);
//对前1000个数先排序
quickSort($topArr,0,999);
for ($i = 1000; $i < 1370000; $i++){
    if ($topArr[0] > $allArr[$i]){
        continue;
    }

    $topArr[0] = $allArr[$i];
    quickSort($topArr,0,999);
}
//时间复杂度是n*logm  （n=1370000,m=1000）
var_dump($topArr);

$elapsed = microtime(true) - $start;
echo "That took $elapsed seconds.\n";
